from collections import deque
n, m=[int(k) for k in input().split()]
w=[]
for j in range(m):
w.append([int(k) for k in input().split()])
q={}
for j in w:
if j[0] in q:
q[j[0]].append(j[1])
else:
q[j[0]]=[j[1]]
if j[1] in q:
q[j[1]].append(j[0])
else:
q[j[1]]=[j[0]]
res=[]
eta=[]
rho=[]
iota=list(q.keys())
epsilon=set(iota)
for j in range(1, n+1):
if j not in epsilon:
rho.append(j)
check=set()
for j in iota:
if j not in check:
new=deque([j])
check.add(j)
eta.append([j])
zeta=1
while new:
x=new.pop()
for k in q[x]:
if k not in check:
new.appendleft(k)
check.add(k)
zeta+=1
eta[-1].append(k)
res.append(zeta)
if zeta>3:
break
if zeta==2:
if rho:
eta[-1].append(rho.pop())
else:
res.append(4)
break
for j in res:
if j>3:
print(-1)
break
else:
for j in eta:
print(" ".join([str(k) for k in j]))
while rho:
print(rho.pop(), rho.pop(), rho.pop())#include <bits/stdc++.h>
#define ll long long int
#define ld long double
#define pb push_back
#define fi first
#define se second
#define MOD 1000000007
#define pi 3.141592653
#define N 100005
using namespace std;
int dx[9]={1, -1, 0, 0, 1, 1, -1, -1, 0};
int dy[9]={0, 0, 1, -1, 1, -1, 1, -1, 0};
bool vis[N/2000];
vector<int> cc[N/2000];
int cnt;
void dfs (vector<int> g[], int t)
{
vis[t]=true;
cc[cnt].pb(t);
for(int i=0; i<g[t].size(); i++)
{
if(vis[g[t][i]]==false) dfs(g, g[t][i]);
}
}
int main()
{
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int n, m, i, j;
cnt=0;
cin>>n>>m;
vector<int> g[N/2000];
vector< vector<int> > ans;
for(i=1; i<=m; i++)
{
int u, v;
cin>>u>>v;
g[u].pb(v); g[v].pb(u);
}
for(i=0; i<=n; i++) vis[i]=false;
for(i=1; i<=n; i++)
{
if(vis[i]==false)
{
dfs(g, i);
cnt++;
}
}
for(i=0; i<cnt; i++)
{
if(cc[i].size()>3) break;
}
if(i<cnt) cout<<-1;
else{
int c1=0, c2=0;
for(i=0; i<cnt; i++)
{
if(cc[i].size()==1) c1++;
else if(cc[i].size()==2) c2++;
}
vector<int> one;
for(i=0; i<cnt; i++)
{
if(cc[i].size()==1) one.pb(cc[i][0]);
}
if(c1<c2) cout<<-1;
else{
for(i=0; i<cnt; i++)
{
if(cc[i].size()==2) ans.pb(cc[i]);
}
for(i=0; i<ans.size(); i++) ans[i].pb(one[i]);
for(i=ans.size(); i<one.size(); i=i+3) ans.pb({one[i], one[i+1], one[i+2]});
for(i=0; i<cnt; i++)
{
if(cc[i].size()==3) ans.pb(cc[i]);
}
for(i=0; i<ans.size(); i++)
{
for(j=0; j<ans[i].size(); j++)
cout<<ans[i][j]<<" ";
cout<<"\n";
}
}
}
return 0;
}1728D - Letter Picking | 792B - Counting-out Rhyme |
1195A - Drinks Choosing | 5D - Follow Traffic Rules |
1272A - Three Friends | 1632D - New Year Concert |
1400D - Zigzags | 716C - Plus and Square Root |
412A - Poster | 844B - Rectangles |
1591A - Life of a Flower | 1398C - Good Subarrays |
629A - Far Relative’s Birthday Cake | 1166A - Silent Classroom |
1000B - Light It Up | 218B - Airport |
1463B - Find The Array | 1538C - Number of Pairs |
621B - Wet Shark and Bishops | 476B - Dreamoon and WiFi |
152C - Pocket Book | 1681D - Required Length |
1725D - Deducing Sortability | 1501A - Alexey and Train |
721B - Passwords | 1263D - Secret Passwords |
1371B - Magical Calendar | 1726E - Almost Perfect |
1360C - Similar Pairs | 900A - Find Extra One |